package Study;

import org.junit.Test;

import java.util.*;

public class Knowledge2 {
    @Test
    public void test1() {
        int[] a = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(maxArea(a));
    }

    public int maxArea(int[] height) {
        //贪心算法
        int l = 0;
        int r = height.length - 1;
        int ans = 0;
        while (l < r) {
            ans = height[l] < height[r] ?
                    Math.max(ans, (r - l) * height[l++]) :
                    Math.max(ans, (r - l) * height[r--]);
        }
        return ans;
    }

    @Test
    public void test2() {
        int[] a = {0, 2, 3};
        System.out.println(canJump(a));
    }

    public boolean canJump(int[] nums) {
        //数组的长度
        int len = nums.length;
        //设置一个最大值
        int max = 0;
        for (int i = 0; i < len; i++) {
            if (i <= max) {
                max = Math.max(i + nums[i], max);
                if (max >= len - 1) return true;
            }
        }
        return false;
    }

    public boolean canJump2(int[] nums) {
        //数组的长度
        int len = nums.length;
         /*
        定义一个cover，表示当前元素能跳的最大覆盖范围，每次我都只往右跳一格
        然后更新cover范围，将当前索引的覆盖范围和上一次的覆盖范围cover相比，
        两者中的最大值就是更新后的cover。当最大范围>=数组最后一个索引时，返回true
         */
        int cover = 0;
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(cover, nums[i] + i);
            if (cover > len - 1) return true;
        }
        return false;
    }

    @Test
    public void test3() {
        int[] a = {0, 2, 3};
        System.out.println(jump(a));
    }

    public int jump(int[] nums) {
        int len = nums.length;
        //初始步数为0
        int count = 0;
        //当前点可以覆盖的范围
        int curCover = 0;
        //最大覆盖范围
        int maxCover = 0;
        for (int i = 0; i < len; i++) {
            //在可覆盖的范围内更新最大的覆盖范围
            maxCover = Math.max(maxCover, i + nums[i]);
            //如果最大覆盖范围大于等于数组的长度  说明可以跳到最后
            if (maxCover >= len - 1) {
                count++;
                break;
            }
            //如果移动的下标到达本次覆盖的最大值以后还没有到达最后位置 则需要加一步 并更换当前可覆盖范围
            if (i == curCover) {
                //分两种情况 如果当前位置
                count++;
                curCover = maxCover;
            }
        }
        return count;
    }


    @Test
    public void test4() {
        int[] a = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit2(a));
    }

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (prices == null || len < 2) return 0;
        //利润
        int profits = 0;
        //总利润
        int sum = 0;
        //默认第一个值为最大价格
        int max = prices[0];
        //默认第一个值为最小价格
        int min = prices[0];
        for (int i = 1; i < len; i++) {
            //如果当前价格小于最大价格
            if (prices[i] < max) {
                //利润等于最大价格-最小价格
                profits = max - min;
                //总利润
                sum += profits;
                //将此值给最大值
                max = prices[i];
                //将此值给最小值
                min = prices[i];
            } else {
                max = prices[i];
                if (i == len - 1) sum += (max - min);
            }
        }
        return sum;
    }

    public int maxProfit2(int[] prices) {
        int len = prices.length;
        if (prices == null || len < 2) return 0;
        int sum = 0;
        for (int i = 1; i < len; i++) {
            int diff = prices[i] - prices[i - 1];
            if (diff > 0) {
                sum += diff;
            }
        }
        return sum;
    }

    @Test
    public void test5() {
        int[] gas = {5, 1, 2, 3, 4};
        int[] cost = {4, 4, 1, 5, 1};
        System.out.println(canCompleteCircuit(gas, cost));
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        //加油站的长度
        int len = gas.length;
        //当前位置
        int i = 0;
        //因为循环到最后位置需要从头开始 走过步数相当于加油站的个数
        int count = 0;
        int residueOil, sumOil = 0;
        while (i % len < len) {
            //如果第一次 选的加油站的汽油容量小于第一次去下个加油站的耗油量
            //通过是否走过  来判断是否是第一次
            if (count == 0) {
                if (gas[i % len] < cost[i % len]) {
                    i++;
                    //如果没到最后 直接跳过选下一个 否则直接结束
                    if (i < len) continue;
                    break;
                } else {
                    sumOil = gas[i % len];
                }
            }
            //剩余油量
            residueOil = sumOil - cost[i % len];
            if (residueOil < 0) {
                count = 0;
                continue;
            }
            //总油量
            sumOil = residueOil + gas[(i + 1) % len];
            i++;
            count++;
            if (count == len) return i % len;
        }
        return -1;
    }

    @Test
    public void test6() {
        int[] ratings = {1};
        System.out.println(candy(ratings));
    }

    public int candy(int[] ratings) {
        //定义糖的总数量
        int sum = 0;
        //数组的长度
        int len = ratings.length;
        //建一个新的左数组
        int[] left = new int[len];
        //建一个新的右数组
        int[] right = new int[len];
        //先建左右数组中的糖的数量都设置为1
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);

        for (int i = 1; i < len; i++) {
            //如果left数组中 右边的数大于左边的数  糖的数量+1
            if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;

        }
        for (int i = len - 2; i >= 0; i--) {
            //如果right数组中 左边的数大于右边的数  糖的数量+1
            if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
        }

        for (int i = 0; i < len; i++) {
            sum += Math.max(left[i], right[i]);
        }

        return sum;
    }

    @Test
    public void test7() {
        int[] nums = {21, 0, 0};
        System.out.println(largestNumber(nums));
    }

    public String largestNumber(int[] nums) {
        int len = nums.length;
        String[] ss = new String[len];
        for (int i = 0; i < len; i++) {
            ss[i] = "" + nums[i];
        }
        Arrays.sort(ss, (a, b) -> {
            String sa = a + b, sb = b + a;
            return sb.compareTo(sa);
        });
        StringBuilder sb = new StringBuilder();
        for (String s : ss) {
            sb.append(s);
        }
        int length = sb.length();
        int k = 0;
        while (k < length - 1 && sb.charAt(k) == '0') {
            k++;
        }
        return sb.substring(k);
    }

    @Test
    public void test8() {
        System.out.println(removeKdigits("14322195", 3));
    }

    public String removeKdigits(String num, int k) {
        //字符串的长度
        int len = num.length();
        //如果字符串的长度等于k的长度直接返回0
        if (len == k) return "0";
        //创建单调栈
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            //取得当前字符
            char c = num.charAt(i);
            //如果单调栈中有数据的话  比较当前数据和单调栈的最后一个数据  当 当前数据小于单调栈栈最后的一个数据时 并且k>0时 删除最后一个数据 k-1
            while (sb.length() > 0 && sb.charAt(sb.length() - 1) > c && k > 0) {
                --k;
                sb.deleteCharAt(sb.length() - 1);
            }
            sb.append(c);
        }
        //有可能数字是递增的 所以在上面的操作中没有删除k个数据   所以要把后面的k个数据删除
        while (k-- > 0) sb.deleteCharAt(sb.length() - 1);
        //因为不能输出前导0 所以如果前导有0的话 需要排除
        while (!"0".equals(sb.toString()) && sb.charAt(0) == '0') sb.deleteCharAt(0);
        return sb.toString();
    }

    @Test
    public void test9() {
        System.out.println(removeDuplicateLetters2("bcac"));
    }

    public String removeDuplicateLetters(String s) {
        /*
         * 1、去重
         * 2、保证相对顺序
         * 3、字典序最小
         * */
        //存放去重的结果
        Stack<Character> stack = new Stack<>();
        //创建一个int数组 维护字符出现的次数
        int[] count = new int[256];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
        }
        //boolean类型的数组 初始值为false 用来记录栈中是否已经存在某个字符  基本数据类型默认值为false 包装类的默认值是null
        boolean[] inStack = new boolean[256];
        for (char c : s.toCharArray()) {
            //遍历过的字符数量减1
            count[c]--;
            //如果栈中已经存在了某个字符  直接跳过
            if (inStack[c]) continue;
            //如果当前字符的字典序小于上一个 把上一个替换掉即 栈中将其弹出  并将数组中该字符boolean改为false
            while (!stack.empty() && c < stack.peek()) {
                //如果栈顶字符后续不存在了 将不再替换  eg：bcac
                if (count[stack.peek()] == 0) {
                    break;//结束的是while这层循环
                } else {
                    inStack[stack.pop()] = false;
                }
            }
            //如果栈中没有此字符 将其添加进去  并将数组中该字符boolean改为true
            stack.push(c);
            inStack[c] = true;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.empty()) {
            //从栈顶将字符放入到stringBuilder中
            sb.append(stack.pop());
        }
        //栈中元素插入顺序是反的 需要reverse反转一下
        return sb.reverse().toString();
    }

    @Test
    public void test10() {
        int[] nums = {5, 4, 3, 2, 1};
        System.out.println(increasingTriplet(nums));
    }

    public boolean increasingTriplet(int[] nums) {
        int a = Integer.MAX_VALUE, b = a;
        for (int num : nums) {
            if (num <= a) {
                a = num;
            } else if (num <= b) {
                b = num;
            } else {
                return true;
            }
        }
        return false;
    }

    public boolean increasingTriplet2(int[] nums) {
        if (nums == null || nums.length < 3) return false;
        int j = 0;
        int i = 0;
        Stack<Integer> stack = new Stack<>();
        for (; i < nums.length; i++) {
            if (stack.empty()) {
                stack.push(nums[i]);
            } else if (nums[i] > stack.peek()) {
                stack.push(nums[i]);
            } else if (nums[i] <= stack.peek()) {
                if (j == 0) {
                    j = i;
                } else {
                    j = Math.min(j, i);
                }
                if (stack.size() > 1) {
                    Integer pop = stack.pop();
                    if (nums[i] > stack.peek()) {
                        stack.push(nums[i]);
                    } else {
                        stack.push(pop);
                    }
                }
            }
            if (stack.size() == 3) {
                return true;
            } else if (i == nums.length - 1) {
                if (nums.length - j < 3) break;
                i = --j;
                stack = new Stack<>();
                j = 0;
            }
        }
        return false;
    }

    public boolean increasingTriplet3(int[] nums) {
        /*
         * 双向遍历
         * */
        //数组的长度
        int len = nums.length;
        //如果数组为空 或者数组的的长度 小于3 直接false
        if (nums == null || nums.length < 3) return false;
        //创建一个左边最小数组   因为对于nums[i]只要其左边的最小数小于它 即复合递增
        int[] leftMin = new int[len];
        leftMin[0] = nums[0];
        for (int i = 1; i < len; i++) {
            leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
        }
        //创建一个右边最大数组    因为对于nums[i]只要其右边的最大数大于它 即复合递增
        int[] rightMax = new int[len];
        rightMax[len - 1] = nums[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
        }
        //上边两个数组的遍历 就能获得对于nums[i]来说 左边的最小值 和右边的最大值
        //只有有一个i 复合 nums[i]大于左边的最小数   小于右边的最大数 即符合递增
        for (int i = 1; i < len - 1; i++) {
            if (nums[i] > leftMin[i - 1] && nums[i] < rightMax[i + 1]) return true;
        }
        return false;
    }

    public boolean increasingTriplet4(int[] nums) {
        int len = nums.length;
        //如果数组为空 或者数组的的长度 小于3 直接false
        if (nums == null || nums.length < 3) return false;
        int first = nums[0], second = Integer.MAX_VALUE;
        for (int i = 1; i < len; i++) {
            if (nums[i] > second) {
                return true;
            } else if (nums[i] > first) {
                second = nums[i];
            } else {
                first = nums[i];
            }
        }
        return false;
    }

    public String removeDuplicateLetters2(String s) {

        int len = s.length();
        //将字符串中字符出现的次数 统计出来
        int[] count = new int[256];
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            count[s.charAt(i)]++;
        }
        //创建一个栈 用来放去除重复字母之后的字符
        Stack<Character> stack = new Stack<>();
        //创建一个Boolean类型的数组  可以判断某个字符是否已经存在  boolean 默认是false
        boolean[] isStack = new boolean[256];
        for (char c : s.toCharArray()) {
            //循环一次字符的次数减少一次
            count[c]--;
            //如果字符 是存在的 直接跳过
            if (isStack[c]) continue;
            //如果栈不是空的 并且 当前的字符字典序 小于栈中最后字符
            while (!stack.empty() && c < stack.peek()) {
                if (count[stack.peek()] == 0) {
                    break;
                } else {
                    isStack[stack.pop()] = false;
                }
            }
            stack.push(c);
            isStack[c] = true;
        }
        StringBuilder sb = new StringBuilder();
        //从栈顶将元素 放入到stringBuilder中
        while (!stack.empty()) sb.append(stack.pop());
        return sb.reverse().toString();
    }

    @Test
    public void test11() {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.println(wiggleMaxLength(nums));
    }

    public int wiggleMaxLength(int[] nums) {
        int len = nums.length;
        if (len < 2) return len;
        int cur = 1;
        Stack<Integer> stack = new Stack<>();
        stack.push(nums[0]);
        for (int i = 1, curr; i < len; i++) {
            if (nums[i] - nums[i - 1] > 0) {
                curr = 1;
            } else if (nums[i] - nums[i - 1] < 0) {
                curr = -1;
            } else {
                stack.pop();
                stack.push(nums[i]);
                continue;
            }
            if (stack.size() > 1 && curr != cur) {
                stack.pop();
            }
            stack.push(nums[i]);
            cur = -curr;
        }
        return stack.size();
    }

    public int wiggleMaxLength2(int[] nums) {
        int len = nums.length;
        if (len < 2) return len;
        //定义增值数 减值数都为1
        int up = 1, down = 1;
        //从1 开始循环
        for (int i = 1; i < len; i++) {
            if (nums[i] - nums[i - 1] > 0) {
                up = down + 1;
            }
            if (nums[i] - nums[i - 1] < 0) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }


    @Test
    public void test12() {
//        System.out.println(integerReplacement2(15));
        System.out.println(15 >> 2);
        int i = 3 & 1;
        System.out.println(i);
    }


    public int integerReplacement(int n) {
        int count = 0;
        return integerReplace(count, (long) n);

    }

    public int integerReplacement2(int _n) {
        long n = _n;
        int ans = 0;
        while (n != 1) {
            if (n % 2 == 0) {
                n >>= 1;
            } else {
                if (n != 3 && ((n >> 1) & 1) == 1) {
                    n++;
                } else {
                    n--;
                }
            }
            ans++;
        }
        return ans;
    }

    public int integerReplace(int count, long n) {
        if (n == 1) return count;
        count++;
        if (n % 2 == 0) {
            n = n >> 1;
            return integerReplace(count, n);
        } else {
            return Math.min(integerReplace(count, n + 1), integerReplace(count, n - 1));
        }
    }

    public String removeKdigits2(String num, int k) {
        int len = num.length();
        if (len == k) return "0";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            char c = num.charAt(i);
            while (sb.length() > 0 && sb.charAt(sb.length() - 1) > c && k > 0) {
                k--;
                sb.deleteCharAt(sb.length() - 1);
            }
            sb.append(c);
        }
        while (k-- > 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
        while (!"0".equals(sb.toString()) && sb.charAt(0) == '0') sb.deleteCharAt(0);
        return sb.toString();
    }

    @Test
    public void test13() {
        int[][] ints = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
        System.out.println(reconstructQueue(ints));
    }

    public int[][] reconstructQueue(int[][] people) {
        //首先需要按身高倒叙排序  当身高一样的时候按照前面人数的多少排序
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });

        LinkedList<int[]> list = new LinkedList<>();
        //然后将数组中的数据放入到新的数组中   排好序后  后面的数据插入的时候不会影响前面的数据
        //将后面的数据把v中的数字取出来
        for (int[] person : people) {
            list.add(person[1], person);
        }

        return list.toArray(new int[people.length][]);
    }

    @Test
    public void test14() {
        String s = "aaaaaccc";
        System.out.println(longestPalindrome(s));
    }

    public int longestPalindrome(String s) {
        //创建一个存储数字的数组
        int[] count = new int[128];
        //字符串的长度
        int len = s.length();
        //将字符出现的次数 存储到数组中
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            count[c]++;
        }
        //定义一个ans 来存储回文串的长度
        int ans = 0;

        for (int v : count) {
            //回文串  就是最多只能有一个字符出现奇数次 其它都出现偶数次
            //假如是字符出现的是偶数次 eg：4  -> 4   5 -> 4
            ans += v / 2 * 2;
            //ans 一直是偶数 直到出现奇数的字符  这个时候ans加1 ans会变成奇数
            if (v % 2 == 1 && ans % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }

    @Test
    public void test15() {
        int[] count = new int[128];
        count['a'] = 2;
        System.out.println(count['a']);
    }


    @Test
    public void test16() {
        int[] nums = {20, 30, 55, 67, 79, 81, 97, 100};
        int index = binarySearch(nums, 81);
        System.out.println(index);
    }

    private int binarySearch(int[] nums, int i) {
        int start = 0;
        int end = nums.length - 1;

        //二分查找法
        while (start < end) {
            int mid = (start + end) >> 1;
            if (nums[mid] < i) { //如果中间数 小于目标值 应该在右边区域
                start = mid + 1;
            } else if (nums[mid] > i) {
                end = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    @Test
    public void test17() {
        int[] nums = {7, 5, 2, 10, 8};
        int sBig = splitArray(nums, 2);
        System.out.println(sBig);
    }

    public int splitArray(int[] nums, int k) {
        long left = 0;
        long right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }

        while (left < right) {
            long mid = (left + right) >> 1;
            int count = 0;
            long sum = 0;
            for (int num : nums) {
                if (sum + num > mid) {
                    sum = 0;
                    count++;
                }
                sum += num;
            }
            //最后一次的话有可能不会走循环
            count++;
            if (count > k) {//说明容量小了 应该 扩大容量
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return (int) left;
    }


    /**
     * 记录连续出现的字符 起始和终止坐标
     */
    class SameChar {
        int st;
        int en;
        char c;

        SameChar(int st, int en, char c) {
            this.st = st;
            this.en = en;
            this.c = c;
        }

    }


    public int strongPasswordChecker(String password) {
        //统计小写字符
        int lowerCase = 0;
        //统计大写字符
        int upperCase = 0;
        //统计数字
        int number = 0;
        //统计连续字符出现的位置
        ArrayList<SameChar> sameChars = new ArrayList<>();
        char[] chars = password.toCharArray();
        if (chars.length == 0) {
            return 6;
        }
        //记录连续出现的字符
        SameChar sameChar = new SameChar(0, 0, '\0');
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] >= 'a' && chars[i] <= 'z') {
                lowerCase++;
            } else if (chars[i] >= 'A' && chars[i] <= 'Z') {
                upperCase++;
            } else if (chars[i] >= '0' && chars[i] < '9') {
                number++;
            }
            if (sameChar.c != chars[i]) {
                if (sameChar.en - sameChar.st >= 2) {
                    sameChars.add(new SameChar(sameChar.st, sameChar.en, sameChar.c));
                }
                sameChar.c = chars[i];
                sameChar.st = i;
                sameChar.en = i;
            } else {
                sameChar.en = i;
            }
        }
        return 1;
    }


    @Test
    public void test18() {

        int[][] ints = {{1, 2}, {3, 4}, {2, 3}, {1, 3}};
        eraseOverlapIntervals(ints);
    }


    public int eraseOverlapIntervals(int[][] intervals) {

        //先将区间按照右区间  从小到大排序
        Arrays.sort(intervals, (a, b) -> {
            if (a[1] == b[1]) return a[0] - b[0];
            return a[1] - b[1];
        });
        if (intervals.length == 0) return 0;
        //记录非交叉区间的个数
        int count = 1;
        //记录区间分割点
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (end <= intervals[i][0]) {
                end = intervals[i][1];
                count++;
            }
        }

        return intervals.length - count;
    }


    @Test
    public void test19() {

        int[][] ints = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
        Arrays.sort(ints, (a, b) -> {
            return Integer.compare(b[0], a[0]);
        });
        for (int[] anInt : ints) {
            System.out.println(anInt[0]);
        }
    }

    @Test
    public void test20() {

        int[][] ints = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
        System.out.println(findMinArrowShots(ints));
    }


    public int findMinArrowShots(int[][] points) {
        //数组的长度
        int len = points.length;
        if (len == 0) return 0;
        //将数组的右边界 从小到大排序
        Arrays.sort(points, (a, b) -> {
            if (a[1] == b[1]) return Integer.compare(a[0], b[0]);
            return Integer.compare(a[1], b[1]);
        });

        //次数
        int count = 1;
        int end = points[0][1];
        for (int i = 1; i < len; i++) {
            if (points[i][0] > end) {
                count++;
                end = points[i][1];
            }
            if (points[i][1] < end) end = points[i][1];
        }
        return count;
    }

    @Test
    public void test21() {

        int[] g = {2, 8, 1};
        int[] s = {4, 7, 6};
        System.out.println(findContentChildren(g, s));
    }

    public int findContentChildren(int[] g, int[] s) {
        //首先将孩子的胃口按从小到大排序   将饼干也按照从小到大排序
        Arrays.sort(g);
        Arrays.sort(s);
        //孩子的数量
        int child = 0;
        //饼干的数量
        int cookie = 0;
        while (child < g.length && cookie < s.length) {
            if (g[child] <= s[cookie]) { //如果饼干可以满足孩子  孩子的数量+1
                child++;
            }
            //饼干的数量每次都需要+1  如果小于孩子的胃口  直接丢弃  ，如果满足孩子的胃口  直接让孩子吃掉
            cookie++;
        }
        return child;
    }


    @Test
    public void test22() {
        int k = 2, w = 0;
        int[] profits = {1, 2, 3};
        int[] capital = {0, 1, 1};
        System.out.println(findMaximizedCapital(k, w, profits, capital));
    }

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int len = profits.length;
        //建立新数组
        int[][] arr = new int[len][2];
        int curr = 0;
        //将项目的启动资金和净利润 合到一起 放到数组中
        for (int i = 0; i < len; i++) {
            arr[i][0] = capital[i];
            arr[i][1] = profits[i];
        }
        Arrays.sort(arr, (a, b) -> {
            return Integer.compare(a[0], b[0]);
        });
        //将
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            while (curr < len && arr[curr][0] <= w) {
                pq.add(arr[curr][1]);
                curr++;
            }
            if (!pq.isEmpty()) {
                w += pq.poll();
            } else {
                break;
            }
        }
        return w;
    }

    @Test
    public void test23() {
        PriorityQueue<Integer> pq = new PriorityQueue<>(/*(x,y)->y-x*/);
        pq.add(1);
        pq.add(6);
        pq.add(2);
        pq.add(5);
        pq.add(8);
        pq.add(3);
        pq.add(9);
        int size = pq.size();
        System.out.println("第一次队列中的数据:" + pq);
        for (int i = 0; i < size; i++) {
            System.out.println(pq.poll());
            System.out.println("第二次队列中的数据:" + pq);
        }
    }


    @Test
    public void test24() {
        int[] nums = {6, 2, 6, 5, 1, 2};
        System.out.println(arrayPairSum(nums));
    }

    public int arrayPairSum(int[] nums) {

        //降序排序
        Arrays.sort(nums);
        int len = nums.length;
        Integer[] numss = new Integer[len];
        for (int i = 0; i < len; i++) {
            numss[i] = nums[len - 1 - i];
        }
        int[][] arr = new int[len / 2][2];
        int cur = 0;
        int sum = 0;
        int twoMin = Integer.MAX_VALUE;

        while (cur < len) {
            twoMin = Math.min(twoMin, numss[cur]);
            if (cur % 2 == 1) {
                sum += twoMin;
                twoMin = Integer.MAX_VALUE;
            }
            cur++;
        }

        return sum;
    }

    @Test
    public void test25() {
        int[] nums = {1, 2, 3, 4};
        System.out.println(findUnsortedSubarray(nums));
    }

    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        int numss[] = new int[len];
        for (int i = 0; i < len; i++) {
            numss[i] = nums[i];
        }
        //将数组按照从小到大的顺序排序
        Arrays.sort(numss);
        //比较两个数组中的不同
        int start = 0, end = 0, cur = 0;
        for (int i = 0; i < len; i++) {
            if (cur == 0 && numss[i] != nums[i]) {
                start = i;
                cur++;
            }
            if (numss[i] != nums[i]) end = i;
        }

        return (end - start) == 0 ? 0 : (end - start + 1);
    }

    @Test
    public void test26() {
        int[] nums = {1, 0, 0, 0, 1};
        System.out.println(canPlaceFlowers(nums, 2));
    }

    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        //花床的长度
        int len = flowerbed.length;
        //如果新的花种完了 或者花床已经用完了  停止遍历
        for (int i = 0; i < len && n > 0; ) {
            //如果当前位置已经种植了的话 那么下一个可以种花的位置是i+2
            if (flowerbed[i] == 1) {
                i += 2;
                //如果是最后一个位置肯定可以种植
                //如果不是最后一个位置 但是它的下一个位置也没有种植的话 那么此位置也可以种植
            } else if (i == len - 1 || flowerbed[i + 1] == 0) {
                //将花的个数减一
                n--;
                //同时找出下一个可以种植花的位置
                i += 2;
                //这是找到种植的位置 但是它的下一个位置已经存在花了 所以不能再种植花 直接找下一个位置
            } else {
                //下一个位置是当前位置+1(有花的位置)再+1(相邻的位置不能再种花)再+1  即+3
                i += 3;
            }
        }
        //如果最后花的个数用完了 返回true
        return n <= 0;

    }

    @Test
    public void test27() {
        int[] nums = {2, 3, 4, 5};
        System.out.println(triangleNumber(nums));
    }

    @Test
    public void test28() {
        Integer a = 5;
        Long b = 5L;
        System.out.println(a.equals(b));
        System.out.println(a == b.intValue());
    }

    public boolean canPlaceFlowersv2(int[] flowerbed, int n) {

        return Boolean.FALSE;
    }
/*
/*
*    2,3,4,5
*    0 1 2 3
*
*    i j
*    k
* */

    public int triangleNumber(int[] nums) {
        //数组的长度
        int len = nums.length;
        //将数组排序  形成三角形的条件是两边之后大于第三边 排序之后 只需确保前两边之和大于第三边即可
        Arrays.sort(nums);
        //可组成三角形的数量
        int ans = 0;
        //先从第一个边开始
        for (int i = 0; i < len; i++) {
            //之后的两个边只需要从第一个边之后开始即可
            int k = i;
            for (int j = i + 1; j < len; j++) {
                while (k + 1 < len && nums[k] < nums[i] + nums[j]) {
                    k++;
                }
                ans += Math.max(k - j, 0);
            }
        }
        return ans;
    }

    @Test
    public void test29() {
//        System.out.println();
        char[] tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
        System.out.println(leastInterval(tasks, 2));
    }

    /*
     * * 解题思路：
     * 1、将任务按类型分组，正好A-Z用一个int[26]保存任务类型个数
     * 2、对数组进行排序，优先排列个数（count）最大的任务，
     *    如题得到的时间至少为 retCount =（count-1）* (n+1) + 1 ==> A->X->X->A->X->X->A(X为其他任务或者待命)
     * 3、再排序下一个任务，如果下一个任务B个数和最大任务数一致，
     *    则retCount++ ==> A->B->X->A->B->X->A->B
     * 4、如果空位都插满之后还有任务，那就随便在这些间隔里面插入就可以，因为间隔长度肯定会大于n，在这种情况下就是任务的总数是最小所需时间
     * */
    public int leastInterval(char[] tasks, int n) {
        //任务的数量
        int len = tasks.length;
        if (len <= 1 || n < 1) return len;
        //建立一个长度为26的数组 数组里面保存字符出现的数量
        int[] counts = new int[26];
        //统计字符出现的数量
        for (int i = 0; i < len; i++) {
            //建立的数组是26以内 所以计算的时候减去'A'
            counts[tasks[i] - 'A']++;
        }
        //升序排序
        Arrays.sort(counts);
        //获取出现次数最多的字母
        int maxCount = counts[25];
        //优先排列个数最大的任务 计算规则：(n+1)*count-n
        int retCount = (n + 1) * maxCount - n;
        int i = 24;
        //如果有其它字母 出现的次数与最大数一致
        while (i >= 0 && counts[i] == maxCount) {
            retCount++;
            i--;
        }
        return Math.max(retCount, len);
    }


    @Test
    public void test30() {
        int[][] pairs = {{1, 2}, {2, 3}, {4, 5}};
        System.out.println(findLongestChain(pairs));
    }

    public int findLongestChain(int[][] pairs) {
        //数组的长度
        int len = pairs.length;
        if (len <= 1) return len;
        //将数组进行排序
        Arrays.sort(pairs, (a, b) -> {
            if (a[1] == b[1]) return Integer.compare(a[0], b[0]);
            return Integer.compare(a[1], b[1]);
        });
        //最长数对链
        int ans = 1;
        //第一个数组的右边界
        int r = pairs[0][1];
        for (int i = 1; i < len; i++) {
            //如果此数的左边界小于上一个数的右边界 直接跳过
            if (pairs[i][0] <= r) continue;
            //如果此数左边界大于上一个数的右边界 那么右边界更新
            r = pairs[i][1];
            //最长数对链的长度+1
            ans++;
        }
        return ans;
    }


    @Test
    public void test31() {
        System.out.println(predictPartyVictory("RRDDD"));
    }

    public String predictPartyVictory(String senate) {
        //字符串的长度
        int len = senate.length();
        //创建集合
        //天辉集合
        Queue<Integer> radiant = new LinkedList<Integer>();
        //夜魇集合
        Queue<Integer> dire = new LinkedList<Integer>();
        //将字符的位置放入到指定的集合中
        for (int i = 0; i < len; i++) {
            if (senate.charAt(0) == 'R') {
                radiant.offer(i);
            } else {
                dire.offer(i);
            }
        }
        while (!radiant.isEmpty() && !dire.isEmpty()) {
            int radiantRe = radiant.poll(), direRe = dire.poll();

            if (radiantRe < direRe) {
                radiant.offer(radiantRe);
            } else {
                dire.offer(direRe);
            }
        }

        return radiant.isEmpty() ? "Dire" : "Radiant";
    }

    @Test
    public void test32() {
        int[] nums = {1, 2, 3, 4, 4, 5};
        System.out.println(isPossible(nums));
    }

    /*
    *   这道题得采用贪心策略，就是使序列尽可能的长。但是这种策略好像给人一种错误的感觉，
        比如[1,2,3,3,4,5]，如果采用此策略，将会是[1,2,3,4,5]和剩余的[3]。其实这个策略并不是这么简单的，
        比如它扫描到’1’的时候，由于它的前一个元素’0’不存在以’0’结尾的连续子序列，所以它这是向后寻找两个元素，
        凑成子序列[1,2,3]（这时1，2，3各被消耗了一个）。接着我们就应该访问到’3’，我们又去查询以’2’结尾的
        有没有合法的连续序列，但是没有，所以它此时只能向后寻找两个元素，
        凑出连续子序列[3,4,5]（3，4，5个被消耗了一次），结束访问。

        如果输入[1,2,3,3,4,4,5,5]，刚开始访问'1'，建立[1,2,3]，
        接着访问'3'，建立[3,4,5]
        接着访问'4'，由于第一步建立了[1,2,3]以4 - 1结尾的连续子序列，所以它放入，得到[1,2,3,4]
        接着访问'5'，由于第一步建立了[1,2,3,4]以5 - 1结尾的连续子序列，所以它放入，得到[1,2,3,4,5]
    * */

    public boolean isPossible(int[] nums) {
        //创建一个哈希表统计每个元素出现的次数
        Map<Integer, Integer> countNum = new HashMap<>();
        for (int num : nums) {
            countNum.put(num, countNum.getOrDefault(num, 0) + 1);
        }
        //定义一个哈希表记录最长的子序列
        Map<Integer, Integer> tail = new HashMap<>();
        for (int num : nums) {
            Integer count = countNum.getOrDefault(num, 0);
            //如果某个数使用完了 直接跳过
            if (count <= 0) {
                continue;
            } else if (tail.getOrDefault(num - 1, 0) > 0) {//前面有数字 可以构成以num结尾的子序列
                //此元素的数量-1
                countNum.put(num, count - 1);
                //覆盖当前最长的子序列
                tail.put(num - 1, tail.get(num - 1) - 1);
                //以num结尾的子序列+1
                tail.put(num, tail.getOrDefault(num, 0) + 1);
            } else if (countNum.getOrDefault(num + 1, 0) > 0 && countNum.getOrDefault(num + 2, 0) > 0) {//前面无数字构成子序列  判断后面是否有元素构成子序列
                //此元素的数量-1
                countNum.put(num, count - 1);
                countNum.put(num + 1, countNum.get(num + 1) - 1);
                countNum.put(num + 2, countNum.get(num + 2) - 1);
                //当前以num + 2结尾的子序列 + 1
                tail.put(num + 2, tail.getOrDefault(num + 2, 0) + 1);
            } else { //前后不能构成子序列 直接返回false
                return false;
            }
        }
        return true;
    }

    @Test
    public void test33() {
        maximumSwap(1993);
    }


    public int maximumSwap(int num) {


        return 1;
    }

    //给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
    public ListNode rotateRight(ListNode head, int k) {
        //如果链表为空或者链表的下一个节点为空或者移动的位置为0 返回原链表即可
        if (head == null || head.next == null || k == 0) return head;
        //创建一个新的链表 方便后续
        ListNode tmp = head;
        //计算链表的长度
        int count = 1;
        //最后指针也将指向最后一个位置
        while (tmp.next != null) {
            count++;
            tmp = tmp.next;
        }
        //首尾相连
        tmp.next = head;
        //因为k的长度可能超过链表的长度 所以取其余数即可
        k %= count;
        //原链表的倒数第k+1个指针的下一个节点即是新链表的头节点
        //正数的话即count - 1个指针的下一个节点即新链表的头节点
        for (int i = 0; i < count - k; i++) {
            tmp = tmp.next;//这个位置的下一个位置就是头节点
        }
        ListNode newNode = tmp.next;
        //将链表的尾部断开
        tmp.next = null;
        return newNode;
    }


    /*
    *
    *  //首先看看链表
        if (head == null || head.next == null || k == 0) return head;
        //创建新的方便后续
        ListNode tmp = head;
        //链表的长度
        int count = 1;
        while (tmp.next != null) {
            count++;//计算长度
            tmp = tmp.next;//这样循环结束后 将会到达最后一个位置
        }
        k %= count;
        if (k == 0) return head;
        //将链表首尾相连
        tmp.next = head;
        //当k=count的时候 相当于到了一开始的位置
        //当k>count的时候  应该 k%count 这样可以避免超时
        //原链表的倒数第k+1个的下一个位置就是新链表头节点
        // 正数的话 第count - k的下一个位置就是新链表的头节点
        for (int i = 0; i < count - k; i++) {
            tmp = tmp.next;//这个位置的下一个位置就是新链表的头节点
        }
        ListNode newNode = tmp.next;
        //将环形链 断开
        tmp.next = null;
        return newNode;
    * */
    public void printString(StringBuilder stringBuilder, Object value) {
        if (value instanceof String) {
            System.out.println(stringBuilder.append(",").append(value));
        } else {
            Map valueMap = (Map) value;
            Set<Map.Entry<String, Object>> set = valueMap.entrySet();
            for (Map.Entry<String, Object> objectEntry : set) {
                //每轮循环前 需要将前缀保存下来 同等级的需要使用
                String record = stringBuilder.toString();
                printString(stringBuilder.append("-").append(objectEntry.getKey()), objectEntry.getValue());
                stringBuilder = new StringBuilder(record);
            }
        }
    }

    @Test
    public void test34() {
        Map<String, Object> process = new HashMap<>();
        process.put("1", "1");
        process.put("2", Collections.singletonMap("3", "2"));
        Map<String, Object> sub3 = new HashMap<>();
        sub3.put("sss1", "1");
        Map<String, Object> sub2 = new HashMap<>();
        sub2.put("ss1", sub3);
        sub2.put("ss2", "22");
        Map<String, Object> sub = new HashMap<>();
        sub.put("s1", sub2);
        sub.put("s2", "2");
        sub.put("s3", "3");
        sub.put("s4", "4");
        process.put("4", sub);
        Set<Map.Entry<String, Object>> entries = process.entrySet();
        for (Map.Entry<String, Object> entry : entries) {
            String key = entry.getKey();
            Object value = entry.getValue();
            printString(new StringBuilder(key), value);
        }
// 输出
// key 1 , value 1
// key 2-3  , value  2
// key 4-s1  , value  1
// key 4-s2  , value  2

    }


    @Test
    public void test99() {
        HashMap<Integer, String> map = new HashMap<>();
        map.put(1, "1");
        map.put(2, "2");
        map.put(3, "3");
        map.put(4, "4");
        System.out.println(map);

    }

    @Test
    public void test100() {
        List<Integer> list = Arrays.asList(1, 2, 3);
        System.out.println(list);
        List<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        arrayList.add(4);
        System.out.println(arrayList);
        List<Integer> list1 = arrayList.subList(0, 2);
        System.out.println(list1);
        list1.add(6);
        System.out.println(list1);
        System.out.println(arrayList);
    }

    @Test
    public void test101() {
        TreeNode treeNode = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        System.out.println(inorderTraversal(treeNode));
        System.out.println(inorderTraversal1(treeNode));
        System.out.println(inorderTraversal2(treeNode));
    }

    //先序
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        NLR(root, res);
        return res;
    }

    private void NLR(TreeNode root, List<Integer> res) {
        if (root == null) return;
        res.add(root.val);
        NLR(root.left, res);
        NLR(root.right, res);
    }

    //中序
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        LNR(root, res);
        return res;
    }

    private void LNR(TreeNode root, List<Integer> res) {
        if (root == null) return;
        LNR(root.left, res);
        res.add(root.val);
        LNR(root.right, res);
    }

    //后序
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        LRN(root, res);
        return res;
    }

    private void LRN(TreeNode root, List<Integer> res) {
        if (root == null) return;
        LRN(root.left, res);
        LRN(root.right, res);
        res.add(root.val);
    }

    @Test
    public void test102() {
        TreeNode treeNode = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(8), null)), new TreeNode(3, new TreeNode(6), new TreeNode(7, new TreeNode(9), null)));
        System.out.println(inorderTraversal3(treeNode));
    }

    //中序遍历
    public List<Integer> inorderTraversal3(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) return res;
        while (!stack.isEmpty() || root != null) {
            if (root != null) { //若左子树有值将值放到栈中
                stack.push(root);
                root = root.left;
            } else {
                TreeNode tmp = stack.pop();
                res.add(tmp.val);
                root = tmp.right;
            }
        }
        return res;
    }

    //前序遍历
    public List<Integer> inorderTraversal4(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) return res;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                res.add(root.val);
                stack.push(root);
                root = root.left;
            }
            TreeNode tmp = stack.pop();
            root = tmp.right;
        }
        return res;
    }

    //    //后序遍历
//    public List<Integer> inorderTraversal5(TreeNode root) {
//        LinkedList<Integer> res = new LinkedList<>();
//        Deque<TreeNode> stack = new LinkedList<>();
//        if (root == null) return res;
//        while (!stack.isEmpty() || root != null) {
//            while (root != null) {
//                res.addFirst(root.val);
//                stack.push(root);
//                root = root.right;
//            }
//            TreeNode tmp = stack.pop();
//            root = tmp.left;
//        }
//        return res;
//    }
    //后序  左右根
    public List<Integer> inorderTraversal5(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) return res;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                res.addFirst(root.val);
                stack.push(root);
                root = root.right;
            }
            TreeNode tmp = stack.pop();
            root = tmp.left;
        }
        return res;
    }

    //中序遍历
    public List<Integer> inorderTraversal6(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) return res;
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode tmp = stack.pop();
                res.add(tmp.val);
                root = tmp.right;
            }
        }
        return res;
    }

    //先序遍历
    public List<Integer> inorderTraversal7(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) return res;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                res.add(root.val);
                stack.push(root);
                root = root.left;
            }
            TreeNode tmp = stack.pop();
            root = tmp.right;
        }
        return res;
    }


    @Test
    public void test103() {
        System.out.println(generateTrees(5));
    }

    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> ans = new ArrayList<>();
        if (n == 0) return ans;
        return getAns(1, n);
    }

    private List<TreeNode> getAns(int start, int end) {
        List<TreeNode> ans = new ArrayList<>();
        //此时没有数字 将null值放入到树中
        if (start > end) {
            ans.add(null);
            return ans;
        }
        //只有一个数字 将当前数字作为一棵树 放入到结果中
        if (start == end) {
            TreeNode treeNode = new TreeNode(start);
            ans.add(treeNode);
            return ans;
        }
        //尝试将每个数字作为根节点
        for (int i = start; i <= end; i++) {
            //左子树
            List<TreeNode> leftTrees = getAns(start, i - 1);
            //右子树
            List<TreeNode> rightTrees = getAns(i + 1, end);
            //将两个树两两组合
            for (TreeNode leftTree : leftTrees) {
                for (TreeNode rightTree : rightTrees) {
                    TreeNode treeNode = new TreeNode(i);
                    treeNode.left = leftTree;
                    treeNode.right = rightTree;
                    ans.add(treeNode);
                }
            }
        }
        return ans;

    }

    public List<TreeNode> generateTrees2(int n) {
        //数组类型的数组
        ArrayList<TreeNode>[] dp = new ArrayList[n + 1];
        dp[0] = new ArrayList<TreeNode>(); //如果left或者right为0，就会出现空指针异常
        if (n == 0) return dp[0];
        dp[0].add(null);//如果不加null,那么后面当left或者right为0的时候，就不会执行for循环，而一旦left不执行，right也会被跳过
        //长度为1到n
        for (int len = 1; len <= n; len++) {
            dp[len] = new ArrayList<TreeNode>();
            //将不同的数字作为根节点  只需要考虑到len
            for (int root = 1; root <= len; root++) {
                //左子树的长度  root作为根节点，left是root左边的的节点数
                int left = root - 1;
                //右子树的长度   同理 right是root右边的节点数
                int right = len - root;

                  /*  假设n为5，root是3，那么左边有2个节点，所以去dp[2]里面找，右边也有两个节点4,5。所以还去dp[2]里面找。
                    因为只有dp[2]里面都是2个节点的数。但是dp[2]中的数只有1和2，我们要的是4,5。
                    我们不妨将1,2加上root，你会发现正好是4,5。
                    所以得到结论，左子树的值直接找前面节点数一样的dp索引，右子树的值也找前面一样的dp索引,
                    但是你需要加上root才能保证val是你需要的，所以右子树要重新创建，不然会破坏前面的树。*/

                // 如果dp[left]里有两种可能，dp[right]里有三种可能，那么总共有6种可能。
                for (TreeNode leftTree : dp[left]) {
                    for (TreeNode rightTree : dp[right]) {
                        TreeNode treeRoot = new TreeNode(root); // 这个是每一种可能的root节点。
                        treeRoot.left = leftTree;//左子树可以直接连接
                        //克隆右子树并且加上偏差
                        treeRoot.right = clone(rightTree, root);
                        dp[len].add(treeRoot);//将一种可能加入dp中
                    }
                }
            }
        }
        return dp[n];
    }

    //实现树的复制并且加上偏差
    //offset即偏移量 根节点 左子树 右子树 都加上偏移量
    private TreeNode clone(TreeNode n, int offset) {
        if (n == null) {//如果为null直接返回
            return null;
        }
        TreeNode treeNode = new TreeNode(n.val + offset);//创建节点的时候 加上根节点的数值
        treeNode.left = clone(n.left, offset);//递归左和右
        treeNode.right = clone(n.right, offset);
        return treeNode;
    }

    @Test
    public void test104() {
        System.out.println(numTrees(19));
    }


    public int numTrees(int n) {
        //卡特兰数

        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {//这个j表示选择值为j的值作为根节点
                //1...i  一共i个节点组成排序二叉树   dp[i]   最终计算到dp[n]
                //依次计算以某一个值作为根节点，如  j作为根
                //这种情况下，有   dp[j-1]*[i-j]种树；
                //把所有的情况相加  可以得到i个数 组成排序二叉树的种类数量  最终计算到dp[n]
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }

    long pre = Long.MIN_VALUE;
    //采用中序遍历的方法 因为中序遍历就是递增的
    public boolean isValidBST(TreeNode root) {
        //结束条件 如果root为null，返回true
        //因为空的二叉搜索树也符合条件
        if (root == null) return true;
        //递归访问左子树，获取结果
        boolean leftBoolean = isValidBST(root.left);
        //访问当前节点 如果当前节点小于等于中序遍历前的一个节点，说明不满足BST 返回false;否则继续
        if(root.val <= pre){
            return false;
        }
        //更新pre的值
        pre = root.val;
        //递归访问右子树
        boolean rightBoolean = isValidBST(root.right);
        //左右子树必须都满足二叉搜索树
        return leftBoolean && rightBoolean;

    }

    public void recoverTree(TreeNode root) {
        if(root == null) return;
        List<TreeNode> res = new ArrayList<>();
        //利用中序遍历 获取集合
        inorderTree(root,res);
        //创建两个节点
        TreeNode x = null;
        TreeNode y = null;
        int len = res.size();
        //找出可能出现问题的两个节点
        for (int i = 0; i < len - 1; i++) {
            //如果前节点大于后面的节点说明此时可能存在问题
            if(res.get(i).val > res.get(i+1).val){
                //将后边的节点给y y的值可能会变化 因为两个节点出问题的话 一般情况下会有两处位置顺序相反
                y = res.get(i+1);
                if(x == null){//x的值不会变化 第一次有问题的节点 即不该出现的  大值  节点
                    x = res.get(i);
                }
            }
        }
        //如果xy的值都不为空  将两个节点的值交换即可
        if(x != null && y != null){
            int tmp = x.val;
            x.val = y.val;
            y.val = tmp;
        }
    }

    private void inorderTree(TreeNode root, List<TreeNode> res) {
        if(root == null) return;
        inorderTree(root.left,res);
        res.add(root);
        inorderTree(root.right,res);
    }

    @Test
    public void test105() {
        Deque<Integer>dq = new LinkedList<>();
        dq.push(1);
        dq.push(2);
        dq.push(3);
        dq.push(4);
        int len = dq.size();
        for (int i = 0; i < len; i++) {
            System.out.println(dq.pop());
        }
    }


    private Map<Integer,Integer> map;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //数组的长度  前序数组与中序数组的长度一致
        int len = preorder.length;
        //创建集合  以空间换时间
        map = new HashMap<>(len + 1);
        for (int i = 0; i < len; i++) {
            map.put(inorder[i],i);
        }
        return preTree(preorder,inorder,0,len - 1,0,len - 1);
    }

    private TreeNode preTree(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight) {
        //获取到前序数组中的根节点的值
        int preLeftValue = preorder[preLeft];
        //因为节点的值是唯一的 根据值去找中序数组的位置
        Integer inRoot = map.get(preLeftValue);
        //左子树的长度
        int leftSize = inRoot - inLeft;
        //创建树
        TreeNode treeNode = new TreeNode(preLeftValue);
        //前序的左子树 根节点+1到根节点+左子树的长度  中序的左子树 左节点的位置到根节点的位置-1
        treeNode.left = preTree(preorder,inorder,preLeft + 1,preLeft + leftSize,inLeft,inRoot - 1);
        //前序的右子树  根节点+左子树的长度+1到右节点  中序的右子树  根节点的位置+1 到右节点
        treeNode.right = preTree(preorder,inorder,preLeft + leftSize + 1,preRight,inRoot + 1,inRight);
        return treeNode;
    }
    public int maxDepth (TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;

    }

}
